package com.buddy.learn.algorithm.simple;

import java.util.Arrays;

/**
 * @author Buddy
 * @date 2021/4/20
 */
public class _排序02_快排双边 {

    public static void main(String[] args) {
        int[] arr = {5, 8, 6, 3, 9, 2, 1, 7};
        quickSort(arr, 0, arr.length - 1);

        System.out.println(Arrays.toString(arr));

    }

    /**
     * 快排也是通过交换两个元素的位置实现的
     * 快排在每轮挑选一个基准元素，让比它大的在一端，比他小的，在i另一端
     * 时间复杂度 O(nlogn),最坏情况下 O(n^2)
     *
     * @param arr 数组
     */
    private static void quickSort(int[] arr, int startIndex, int endIndex) {

        if (startIndex >= endIndex) {
            return;
        }

        // 获取基准位置元素
        int pivotIndex = partition(arr, startIndex, endIndex);
        // 根据基准位置排序
        quickSort(arr, startIndex, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, endIndex);

    }

    private static int partition(int[] arr, int startIndex, int endIndex) {
        int left = startIndex;
        int right = endIndex;
        // 取第一个位置的元素作为基准元素
        int pivot = arr[left];
        while (left != right) {
            // 控制right指针比较并左移
            while (left < right && arr[right] > pivot) {
                right--;
            }
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            // 交换left right所指向的元素
            if (left < right) {
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
        }
        //pivot 和 指针重合点交换
        arr[startIndex] = arr[left];
        arr[left] = pivot;
        return left;
    }

}
